#include <iostream>
#include "linkQueue.h"
using namespace std;
template <typename T>
class Node {
public:
	template <typename T>
	friend class binaryTree;
	Node(T value);
	Node(T value, Node<T>* left, Node<T>* right);
	void setLeft(Node<T>* left);
	void setRight(Node<T>* right);
	void set(Node<T>* left,Node<T>* right);
	~Node();
private:
	T value;
	Node<T>* leftChild;
	Node<T>* rightChild;
};
template <typename T>
Node<T>::Node(T value) {
	this->value = value;
	leftChild = nullptr;
	rightChild = nullptr;
}
template <typename T>
Node<T>::~Node() {

}
template <typename T>
Node<T>::Node(T value, Node<T>* left, Node<T>* right) {
	this->value = value;
	leftChild = left;
	rightChild = right;
}
template <typename T>
void Node<T>::setLeft(Node<T>* left) {
	leftChild = left;
}
template <typename T>
void Node<T>::setRight(Node<T>* right) {
	rightChild = right;
}
template <typename T>
void Node<T>::set(Node<T>* left, Node<T>* right) {
	leftChild = left;
	rightChild = right;
}
template <typename T>
class binaryTree {
public:
	binaryTree();
	~binaryTree();
	void inOrderTraverse(Node<T>* root);
	void inverseTraverse(Node<T>* root, ofstream& out, int depth);
	void setRoot(Node<T>* r);
	Node<T>* getRoot();
	void addChild(Node<T>* left, Node<T>* right);
	void numofLeaves(Node<T>* root,int& count);
	void swapChild(Node<T>* root);
	void leveledTraverse(Node<T>* root);
	int widthofBinaryTree(Node<T>* root);
private:
	Node<T>* root;
};
template <typename T>
binaryTree<T>::binaryTree() {
	root = new Node<T>(0);
}
template <typename T>
binaryTree<T>::~binaryTree() {
	delete root;
}
template <typename T>
void binaryTree<T>::addChild(Node<T>* left, Node<T>* right) {
	root->leftChild = left;
	root->rightChild = right;
}
template <typename T>
void binaryTree<T>::setRoot(Node<T>* r) {
	root = r;
}
template <typename T>
Node<T>* binaryTree<T>::getRoot() {
	return root;
}
template <typename T>
void binaryTree<T>::inOrderTraverse(Node<T>* root) {
	if (root == nullptr)return;
	inOrderTraverse(root->leftChild);
	cout << root->value << " ";
	inOrderTraverse(root->rightChild);
}
template <typename T>
void binaryTree<T>::inverseTraverse(Node<T>* root, ofstream& out, int depth) {
	Node<T>* tool = new Node<T>(0, nullptr, nullptr);
	if (root == nullptr)return;
	depth++;
	inverseTraverse(root->rightChild, out, depth);
	for (int i = 1; i < depth; i++)
		out << tool->value << tool->value << tool->value << tool->value << tool->value;
	out << root->value << '\n';
	inverseTraverse(root->leftChild, out, depth);
}
template <typename T>
void binaryTree<T>::numofLeaves(Node<T>* root,int& count) {
	if (root == nullptr) 
		return;
	if (root->leftChild == nullptr && root->rightChild == nullptr)
		count++;
	numofLeaves(root->leftChild,count);
	numofLeaves(root->rightChild,count);
}
template <typename T>
void binaryTree<T>::swapChild(Node<T>* root) {
	if (root == nullptr)return;
	Node<T>* temp = root->leftChild;
	root->leftChild = root->rightChild;
	root->rightChild = temp;
	swapChild(root->leftChild);
	swapChild(root->rightChild);
}
template <typename T>
void binaryTree<T>::leveledTraverse(Node<T>* root) {
	LinkQueue<Node<T>*> q;
	q.Insert(root);
	Node<T>* temp;
	while (!q.IsEmpty()) {
		q.Delete(temp);
		cout << temp->value << " ";
		if(temp->leftChild)
			q.Insert(temp->leftChild);
		if (temp->rightChild)
			q.Insert(temp->rightChild);
	}
	return;
}
template <typename T>
int binaryTree<T>::widthofBinaryTree(Node<T>* root) {
	int width = 1;
	int currentwidth = 1;
	int nextwidth = 0;
	LinkQueue<Node<T>*> q;
	q.Insert(root);
	Node<T>* temp;
	while (!q.IsEmpty()) {
		q.Delete(temp);
		if (currentwidth == 0) {
			currentwidth = nextwidth;
			nextwidth = 0;
		}
		currentwidth--;
		if (temp->leftChild) {
			q.Insert(temp->leftChild);
			nextwidth++;
		}
		if (temp->rightChild) {
			q.Insert(temp->rightChild);
			nextwidth++;
		}
		width = width > nextwidth ? width : nextwidth;
	}
	return width;
}